// CZ 集合类型库
// 提供各种常用的数据结构

const std = @import("std");
const cz_std = @import("cz_std.zig");
const Allocator = cz_std.Allocator;

// ============ LinkedList ============

pub fn LinkedList(comptime T: type) type {
    return struct {
        const Self = @This();
        
        pub const Node = struct {
            data: T,
            next: ?*Node,
            prev: ?*Node,
        };
        
        first: ?*Node,
        last: ?*Node,
        len: usize,
        allocator: Allocator,
        
        pub fn init(allocator: Allocator) Self {
            return Self{
                .first = null,
                .last = null,
                .len = 0,
                .allocator = allocator,
            };
        }
        
        pub fn deinit(self: *Self) void {
            var current = self.first;
            while (current) |node| {
                const next = node.next;
                self.allocator.destroy(node);
                current = next;
            }
        }
        
        pub fn append(self: *Self, value: T) !void {
            const node = try self.allocator.create(Node);
            node.* = Node{
                .data = value,
                .next = null,
                .prev = self.last,
            };
            
            if (self.last) |last| {
                last.next = node;
            } else {
                self.first = node;
            }
            
            self.last = node;
            self.len += 1;
        }
        
        pub fn prepend(self: *Self, value: T) !void {
            const node = try self.allocator.create(Node);
            node.* = Node{
                .data = value,
                .next = self.first,
                .prev = null,
            };
            
            if (self.first) |first| {
                first.prev = node;
            } else {
                self.last = node;
            }
            
            self.first = node;
            self.len += 1;
        }
        
        pub fn popFirst(self: *Self) ?T {
            const node = self.first orelse return null;
            const value = node.data;
            
            self.first = node.next;
            if (self.first) |first| {
                first.prev = null;
            } else {
                self.last = null;
            }
            
            self.allocator.destroy(node);
            self.len -= 1;
            return value;
        }
        
        pub fn popLast(self: *Self) ?T {
            const node = self.last orelse return null;
            const value = node.data;
            
            self.last = node.prev;
            if (self.last) |last| {
                last.next = null;
            } else {
                self.first = null;
            }
            
            self.allocator.destroy(node);
            self.len -= 1;
            return value;
        }
    };
}

// ============ Queue ============

pub fn Queue(comptime T: type) type {
    return struct {
        const Self = @This();
        list: LinkedList(T),
        
        pub fn init(allocator: Allocator) Self {
            return Self{
                .list = LinkedList(T).init(allocator),
            };
        }
        
        pub fn deinit(self: *Self) void {
            self.list.deinit();
        }
        
        pub fn enqueue(self: *Self, value: T) !void {
            try self.list.append(value);
        }
        
        pub fn dequeue(self: *Self) ?T {
            return self.list.popFirst();
        }
        
        pub fn peek(self: *Self) ?T {
            if (self.list.first) |node| {
                return node.data;
            }
            return null;
        }
        
        pub fn len(self: *Self) usize {
            return self.list.len;
        }
        
        pub fn isEmpty(self: *Self) bool {
            return self.list.len == 0;
        }
    };
}

// ============ Stack ============

pub fn Stack(comptime T: type) type {
    return struct {
        const Self = @This();
        list: LinkedList(T),
        
        pub fn init(allocator: Allocator) Self {
            return Self{
                .list = LinkedList(T).init(allocator),
            };
        }
        
        pub fn deinit(self: *Self) void {
            self.list.deinit();
        }
        
        pub fn push(self: *Self, value: T) !void {
            try self.list.prepend(value);
        }
        
        pub fn pop(self: *Self) ?T {
            return self.list.popFirst();
        }
        
        pub fn peek(self: *Self) ?T {
            if (self.list.first) |node| {
                return node.data;
            }
            return null;
        }
        
        pub fn len(self: *Self) usize {
            return self.list.len;
        }
        
        pub fn isEmpty(self: *Self) bool {
            return self.list.len == 0;
        }
    };
}

// ============ HashSet ============

pub fn HashSet(comptime T: type) type {
    return struct {
        const Self = @This();
        map: cz_std.HashMap(T, void),
        
        pub fn init(allocator: Allocator) !Self {
            return Self{
                .map = try cz_std.HashMap(T, void).init(allocator),
            };
        }
        
        pub fn deinit(self: *Self) void {
            self.map.deinit();
        }
        
        pub fn add(self: *Self, value: T) !void {
            try self.map.put(value, {});
        }
        
        pub fn remove(self: *Self, value: T) void {
            _ = self;
            _ = value;
            // TODO: 实现删除
        }
        
        pub fn contains(self: *Self, value: T) bool {
            return self.map.get(value) != null;
        }
        
        pub fn len(self: *Self) usize {
            return self.map.count;
        }
    };
}

// ============ BinaryTree ============

pub fn BinaryTree(comptime T: type) type {
    return struct {
        const Self = @This();
        
        pub const Node = struct {
            data: T,
            left: ?*Node,
            right: ?*Node,
        };
        
        root: ?*Node,
        allocator: Allocator,
        
        pub fn init(allocator: Allocator) Self {
            return Self{
                .root = null,
                .allocator = allocator,
            };
        }
        
        pub fn deinit(self: *Self) void {
            self.destroyNode(self.root);
        }
        
        fn destroyNode(self: *Self, node: ?*Node) void {
            if (node) |n| {
                self.destroyNode(n.left);
                self.destroyNode(n.right);
                self.allocator.destroy(n);
            }
        }
        
        pub fn insert(self: *Self, value: T, comptime lessThan: fn (T, T) bool) !void {
            const node = try self.allocator.create(Node);
            node.* = Node{
                .data = value,
                .left = null,
                .right = null,
            };
            
            if (self.root == null) {
                self.root = node;
                return;
            }
            
            var current = self.root.?;
            while (true) {
                if (lessThan(value, current.data)) {
                    if (current.left) |left| {
                        current = left;
                    } else {
                        current.left = node;
                        return;
                    }
                } else {
                    if (current.right) |right| {
                        current = right;
                    } else {
                        current.right = node;
                        return;
                    }
                }
            }
        }
        
        pub fn contains(self: *Self, value: T, comptime eql: fn (T, T) bool, comptime lessThan: fn (T, T) bool) bool {
            var current = self.root;
            while (current) |node| {
                if (eql(value, node.data)) {
                    return true;
                } else if (lessThan(value, node.data)) {
                    current = node.left;
                } else {
                    current = node.right;
                }
            }
            return false;
        }
    };
}

// ============ PriorityQueue ============

pub fn PriorityQueue(comptime T: type) type {
    return struct {
        const Self = @This();
        items: []T,
        len: usize,
        allocator: Allocator,
        lessThan: *const fn (T, T) bool,
        
        pub fn init(allocator: Allocator, lessThan: *const fn (T, T) bool) !Self {
            const initial_capacity = 16;
            return Self{
                .items = try allocator.alloc(T, initial_capacity),
                .len = 0,
                .allocator = allocator,
                .lessThan = lessThan,
            };
        }
        
        pub fn deinit(self: *Self) void {
            self.allocator.free(self.items);
        }
        
        pub fn add(self: *Self, value: T) !void {
            if (self.len >= self.items.len) {
                try self.ensureCapacity(self.items.len * 2);
            }
            
            self.items[self.len] = value;
            self.len += 1;
            self.siftUp(self.len - 1);
        }
        
        pub fn remove(self: *Self) ?T {
            if (self.len == 0) return null;
            
            const result = self.items[0];
            self.len -= 1;
            
            if (self.len > 0) {
                self.items[0] = self.items[self.len];
                self.siftDown(0);
            }
            
            return result;
        }
        
        pub fn peek(self: *Self) ?T {
            if (self.len == 0) return null;
            return self.items[0];
        }
        
        fn siftUp(self: *Self, index: usize) void {
            var i = index;
            while (i > 0) {
                const parent = (i - 1) / 2;
                if (!self.lessThan(self.items[i], self.items[parent])) break;
                
                const temp = self.items[i];
                self.items[i] = self.items[parent];
                self.items[parent] = temp;
                i = parent;
            }
        }
        
        fn siftDown(self: *Self, index: usize) void {
            var i = index;
            while (true) {
                const left = 2 * i + 1;
                const right = 2 * i + 2;
                var smallest = i;
                
                if (left < self.len and self.lessThan(self.items[left], self.items[smallest])) {
                    smallest = left;
                }
                
                if (right < self.len and self.lessThan(self.items[right], self.items[smallest])) {
                    smallest = right;
                }
                
                if (smallest == i) break;
                
                const temp = self.items[i];
                self.items[i] = self.items[smallest];
                self.items[smallest] = temp;
                i = smallest;
            }
        }
        
        fn ensureCapacity(self: *Self, new_capacity: usize) !void {
            if (new_capacity <= self.items.len) return;
            
            const new_items = try self.allocator.alloc(T, new_capacity);
            for (self.items[0..self.len], 0..) |item, i| {
                new_items[i] = item;
            }
            
            self.allocator.free(self.items);
            self.items = new_items;
        }
    };
}
